package Leetcode.Stack;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/4/18 12:17
 * @Description:
 * 下一个更大元素 IV
 * 困难
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。
 *
 * 如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：
 *
 * j > i
 * nums[j] > nums[i]
 * 恰好存在 一个 k 满足 i < k < j 且 nums[k] > nums[i] 。
 * 如果不存在 nums[j] ，那么第二大整数为 -1 。
 *
 * 比方说，数组 [1, 2, 4, 3] 中，1 的第二大整数是 4 ，2 的第二大整数是 3 ，3 和 4 的第二大整数是 -1 。
 * 请你返回一个整数数组 answer ，其中 answer[i]是 nums[i] 的第二大整数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [2,4,0,9,6]
 * 输出：[9,6,6,-1,-1]
 * 解释：
 * 下标为 0 处：2 的右边，4 是大于 2 的第一个整数，9 是第二个大于 2 的整数。
 * 下标为 1 处：4 的右边，9 是大于 4 的第一个整数，6 是第二个大于 4 的整数。
 * 下标为 2 处：0 的右边，9 是大于 0 的第一个整数，6 是第二个大于 0 的整数。
 * 下标为 3 处：右边不存在大于 9 的整数，所以第二大整数为 -1 。
 * 下标为 4 处：右边不存在大于 6 的整数，所以第二大整数为 -1 。
 * 所以我们返回 [9,6,6,-1,-1] 。
 * 示例 2：
 *
 * 输入：nums = [3,3]
 * 输出：[-1,-1]
 * 解释：
 * 由于每个数右边都没有更大的数，所以我们返回 [-1,-1] 。
 */

public class secondGreaterElement {
    public static void main(String[] args) {
        int[] arr = {2, 4, 0, 9, 6};
        System.out.println(Arrays.toString(secondGreaterElement3(arr)));

    }
    /**
     * 暴力找思路
     * @param nums
     * @return
     */
    public static int[] secondGreaterElement(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return new int[]{-1};
        }
        if (len == 2) {
            return new int[]{-1, -1};
        }
        int[] ans = new int[len];
        Arrays.fill(ans, -1);
        for (int i = 0; i < len - 2; i++) {
            int flag = 0;
            for (int j = i; j < len; j++) {
                if (nums[j] > nums[i]) {
                    if (flag == 1) {
                        ans[i] = nums[j];
                        break;
                    }else{
                        flag++;
                    }
                }
            }
        }
        return ans;
    }

    // Function to find the second greatest element for each element in the array
    public static int[] secondGreaterElement2(int[] nums) {
        // 创建结果数组，并用-1填充，表示如果没有第二大的更大元素则用-1填充
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);

        // 使用一个双端队列（Deque）来存储索引
        Deque<Integer> stack = new ArrayDeque<Integer>();

        // 使用一个优先队列（PriorityQueue），其比较器根据数组的第一个元素进行排序
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);

        // 遍历数组中的每个元素
        for (int i = 0; i < nums.length; ++i) {
            // 当优先队列不为空且当前元素大于优先队列顶部的元素时
            while (!pq.isEmpty() && pq.peek()[0] < nums[i]) {
                // 更新结果数组中对应索引的值为当前元素
                res[pq.poll()[1]] = nums[i];
            }

            // 当栈不为空且栈顶元素小于当前元素时
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                // 将小于当前元素的栈顶元素弹出，并加入优先队列
                pq.offer(new int[]{nums[stack.peek()], stack.peek()});
                stack.pop();
            }
            // 将当前元素的索引压入栈
            stack.push(i);
        }
        // 返回结果数组
        return res;
    }

    // Function to find the second greatest element for each element in the array
    public static int[] secondGreaterElement3(int[] nums) {
        int n = nums.length;
        // 创建结果数组，并用-1填充
        int[] res = new int[n];
        Arrays.fill(res, -1);

        // 使用两个列表来模拟栈
        List<Integer> stack1 = new ArrayList<Integer>();
        List<Integer> stack2 = new ArrayList<Integer>();

        // 遍历数组中的每个元素
        for (int i = 0; i < n; ++i) {
            int v = nums[i];
            // 当栈2不为空且栈2顶部的元素小于当前元素时
            while (!stack2.isEmpty() && nums[stack2.get(stack2.size() - 1)] < v) {
                // 更新结果数组中对应索引的值为当前元素
                res[stack2.get(stack2.size() - 1)] = v;
                // 弹出栈2顶部的元素
                stack2.remove(stack2.size() - 1);
            }
            // 找到栈1中第一个小于或等于当前元素的元素的索引
            int pos = stack1.size() - 1;
            while (pos >= 0 && nums[stack1.get(pos)] < v) {
                --pos;
            }
            // 将栈1中从pos+1到栈顶的元素移到栈2
            for (int j = pos + 1; j < stack1.size(); j++) {
                stack2.add(stack1.get(j));
            }
            // 清空栈1中从pos+1到栈顶的元素
            for (int j = stack1.size() - 1; j >= pos + 1; j--) {
                stack1.remove(j);
            }
            // 将当前元素的索引压入栈1
            stack1.add(i);
        }
        // 返回结果数组
        return res;
    }

}
